// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487246&idx=1&sn=4a514020ce9dc8777e2d1d503188b62b&chksm=9bd7f106aca078108102fe76799983ee8ea3bd759508e6dbfe87bc9da6edbeb8b8dd73deb0d7&scene=178&cur_album_id=1318896187793260544#rd

// 给你输入一个字符串s，你可以在其中的任意位置插入左括号(或者右括号)，请问你最少需要几次插入才能使得s变成一个合法的括号串？

// 比如说输入s = "())("，算法应该返回 2，因为我们至少需要插入两次把s变成"(())()"，这样每个左括号都有一个右括号匹配，s是一个合法的括号串。

class Test {

     // 核心思路是以左括号为基准，通过维护对右括号的需求数need_right，来计算最小的插入次数。
        public int minAddToMakeValid(String s) {
             // need_left 变量记录左括号的需求量
             int need_left = 0;

             // need_right 变量记录右括号的需求量
             int need_right = 0;

             char[] arr = s.toCharArray();

             for (int i = 0; i < arr.length; i++) {
                 if (arr[i] == '(') {
                     // 对右括号的需求 + 1
                     need_right++;
                 }

                 if (arr[i] == ')') {
                     // 对右括号的需求 - 1
                     need_right--;

                     // 右括号太多
                     if (need_right == -1) {
                          need_right = 0;
                          // 需插入一个左括号
                          need_left++;
                      }
                 }
             }

             return need_left + need_right;
        }
}

/*
1、当need_right == -1的时候意味着什么？

因为只有遇到右括号)的时候才会need_right--，need_right == -1意味着右括号太多了，所以需要插入左括号。

比如说s = "))"这种情况，需要插入 2 个左括号，使得s变成"()()"，才是一个合法括号串。
*/

/*
2、算法为什么返回need_left + need_right？

因为need_left记录的左括号的插入次数，need_right记录了右括号的需求，当 for 循环结束后，若need_need_right不为 0，那么就意味着右括号还不够，需要插入。

比如说s = "))("这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得s变成"()()()"，才是一个合法括号串。
*/